/**
//设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。 
//
// 如果指定节点没有对应的“下一个”节点，则返回null。 
//
// 示例 1: 
//
// 输入: root = [2,1,3], p = 1
//
//  2
// / \
//1   3
//
//输出: 2 
//
// 示例 2: 
//
// 输入: root = [5,3,6,2,4,null,null,1], p = 6
//
//      5
//     / \
//    3   6
//   / \
//  2   4
// /   
//1
//
//输出: null 
// Related Topics 树 深度优先搜索 二叉搜索树 二叉树 👍 80 👎 0

*/

package com.xixi.dataStructure.tree.binaryTree;

import com.xixi.dataStructure.tree.TreeNode;

public class ID_InterView_04_06_SuccessorLcci {
public static void main(String[] args) {
Solution solution = new ID_InterView_04_06_SuccessorLcci().new Solution();
}


//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    TreeNode res = null; //结果
    boolean match = false; //找到P就开始剪枝了
    boolean pointbreak = false;
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if(root == null ) return  res;
        res = inorderSuccessor( root.left, p); //中序遍历确保有序
        if(pointbreak) return res;//剪掉右边
        if(match) { //下一个节点
            res = root;
            pointbreak = true;//剪掉右边
            return res;
        }
        if(root.val == p.val) { //这个节点匹配了，match变成true
            match = true;
        }
        res = inorderSuccessor( root.right, p); //中序遍历确保有序

        return  res;
    }


}
//leetcode submit region end(Prohibit modification and deletion)




}